package binarytree

// 递归
func isSymmetric(root *TreeNode) bool {

	return check(root, root)
}

func check(left *TreeNode, right *TreeNode) bool {

	if left == nil {
		return right == nil
	} else if right == nil {
		return left == nil
	}

	if left.Val != right.Val {
		return false
	}
	return check(left.Left, right.Right) && check(left.Right, right.Left)
}

// 迭代
func isSymmetric2(root *TreeNode) bool {

	if root == nil {
		return true
	}

	stack := []*TreeNode{root, root}
	for len(stack) != 0 {
		left := stack[0]
		right := stack[1]
		stack = stack[2:]

		if left.Val != right.Val {
			return false
		}
		if (left.Left != nil && right.Right == nil) || (left.Left == nil && right.Right != nil) {
			return false
		}
		if (left.Right != nil && right.Left == nil) || (left.Right == nil && right.Left != nil) {
			return false
		}
		if left.Left != nil {
			stack = append(stack, left.Left)
			stack = append(stack, right.Right)
		}
		if left.Right != nil {
			stack = append(stack, left.Right)
			stack = append(stack, right.Left)
		}
	}
	return true
}
